/*************************************************************************
	> File Name: merge_sort.cpp
	> Author: 赵江坤
	> Mail: zhaojk90@gmail.com 
	> Created Time: 2013年04月02日 星期二 23时25分39秒
 ************************************************************************/

#include<iostream>
using namespace std;
void merge_sort(int *a,int p,int r);
void merge(int *a,int p,int q,int r);
int main()
{
	int a[]={5,2,4,7,1,3,2,6};
	merge_sort(a,1,8);
	int b[]={2,1};
	merge(b,1,1,2);
	for(int i=0;i<2;i++)
		cout<<b[i]<<" ";
	cout<<endl;
	for(int i=0;i<8;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}



void merge_sort(int *a,int p,int r)
{
	if(p<r)
	{
	int	q=(p+r)/2;
	quick_sort(a,p,q);
	quick_sort(a,q+1,r);
	merge(a,p,q,r);
	}


}


void merge(int *a,int p,int q,int r)
{
	int n1=q-p+1,n2=r-q;
	int *L=new int[n1];
	int *R=new int[n2];
	int i=0,j=0;
	for( i=0;i<n1;i++)
		L[i]=a[p+i-1];
	for(i=0;i<n2;i++)
		R[i]=a[q+i];
	i=0,j=0;
	int k=0;
	for( k=p-1;k<r;k++)
	{
		if(i==n1 || j==n2) break;
		if(L[i]>R[j]){
			a[k]=R[j];
			j++;
		}else{
			a[k]=L[i];
			i++;
		}
	
	}
	if(i!=n1){
		for(;i<n1;i++)
			a[k++]=L[i];	
	}else{
		for(;j<n2;j++)
			a[k++]=R[j];
	}
	delete L;
	delete R;
	return;

}
